#pragma once 
#include <iostream>
#include <map>
#include <set>
#include <assert.h>
#include <math.h>
using namespace std;
namespace cc
{
    template<class K,class V>
    struct AVLnode
    {
        int _bf=0;
        pair<K,V> _val;
        AVLnode<K,V> *_left;
        AVLnode<K,V> *_right;
        AVLnode<K,V> *_parent;
        AVLnode(const pair<K,V>& val=pair<K,V>(),AVLnode<K,V> *left=nullptr,AVLnode<K,V> *right=nullptr,AVLnode<K,V> *parent=nullptr)
            : _val(val)
            , _left(left)
            , _right(right)
            , _parent(parent)
        {}
    };
    template<class K,class V>
    class AVL
    {
    public:
        typedef AVLnode<K,V> node;
        //此parent其实就相当于是旋转点
        void revolveL(node *parent)
        {
            //需要改变的节点
            node *sub=parent->_right;
            node *subl=sub->_left;
            //如果根节点是parent
            if(_root==parent)
            {
                _root=sub;
                sub->_parent=nullptr;
                sub->_left=parent;
                parent->_parent=sub;
                parent->_right=subl;
                if(subl)
                    subl->_parent=parent;
            }
            //此旋转点不是根节点
            else
            {
                node *pparent=parent->_parent;
                if(pparent->_left==parent)
                    pparent->_left=sub;
                else
                    pparent->_right=sub;
                sub->_parent=pparent;
                sub->_left=parent;
                parent->_parent=sub;
                parent->_right=subl;
                if(subl)
                    subl->_parent=parent;
            }
            //旋转完成,更新平衡因子
            sub->_bf=0;
            parent->_bf=0;
        }
        void revolveR(node *parent)
        {
            node *sub=parent->_left;
            node *subr=sub->_right;
            if(_root==parent)
            {
                _root=sub;
                sub->_parent=nullptr;
                sub->_right=parent;
                parent->_parent=sub;
                parent->_left=subr;
                if(subr)
                    subr->_parent=parent;
            }
            else
            {
                node *pparent=parent->_parent;
                if(pparent->_left==parent)
                    pparent->_left=sub;
                else
                    pparent->_right=sub;
                sub->_parent=pparent;
                sub->_right=parent;
                parent->_parent=sub;
                parent->_left=subr;
                if(subr)
                    subr->_parent=parent;
            }
            sub->_bf=0;
            parent->_bf=0;
        }
        bool insert(const pair<K,V>& x)
        {
            //根节点为空
            if(_root==nullptr)
            {
                _root=new node(x);
                //节点中父指针已经指向nullptr
               return true;
            }
            node *parent=nullptr;
            node *cur=_root;
            while(cur)
            {
                if(x.first<(cur->_val).first)
                {
                    parent=cur;
                    cur=cur->_left;
                }
                else if(x.first>(cur->_val).first)
                {
                    parent=cur;
                    cur=cur->_right;
                }
                else
                    return false;
            }
            cur=new node(x);
            if((parent->_val).first>x.first)
                parent->_left=cur;
            else
                parent->_right=cur;
            cur->_parent=parent;
            //插入完成，更新平衡因子
            while(parent)
            {
                if(parent->_right==cur)
                    parent->_bf++;
                else if(parent->_left==cur)
                    parent->_bf--;
                //此情况说明cur既不是做孩子也不是右孩子，所以直接报错，说明插入的时候出现了问题
                else
                    assert(false);
                if(abs(parent->_bf)==0)
                    break;
                else if(abs(parent->_bf)==1)
                {
                    cur=parent;
                    parent=parent->_parent;
                }
                else if(abs(parent->_bf)==2)
                {
                    //旋转
                    if(parent->_bf==2&&cur->_bf==1)
                    {
                        revolveL(parent);   
                    }
                    else if(parent->_bf==-2&&cur->_bf==-1)
                    {
                        revolveR(parent);
                    }
                    else if(parent->_bf==-2&&cur->_bf==1)
                    {
                        node *sub=parent->_left;
                        node *subr=sub->_right;
                        int bf=subr->_bf;
                        revolveL(sub);
                        revolveR(parent);
                        if(bf==0)
                        {
                            parent->_bf=0;
                            sub->_bf=0;
                            subr->_bf=0;
                        }
                        else if(bf==1)
                        {
                            sub->_bf=-1;
                            parent->_bf=0;
                            subr->_bf=0;
                        }
                        else if(bf==-1)
                        {
                            sub->_bf=0;
                            parent->_bf=1;
                            subr->_bf=0;
                        }
                        else
                            assert(false);
                    }
                    else if(parent->_bf==2&&cur->_bf==-1)
                    {
                        node *sub=parent->_right;
                        node *subl=sub->_left;
                        int bf=subl->_bf;
                        revolveR(sub);
                        revolveL(parent);
                        if(bf==0)
                        {
                            subl->_bf=0;
                            sub->_bf=0;
                            parent->_bf=0;
                        }
                        else if(bf==1)
                        {
                            sub->_bf=0;
                            subl->_bf=0;
                            parent->_bf=-1;
                        }
                        else if(bf==-1)
                        {
                            sub->_bf=1;
                            subl->_bf=0;
                            parent->_bf=0;
                        }
                        else 
                            assert(false);
                    }
                    //如果走到这步，说明这棵树的平衡因子有问题
                    else
                        assert(false);
                    break;
                }
                else
                    assert(false);
            }
            return true;
        }
        int high()
        {
            return _high(_root);
        }
        bool check()
        {
            return _check(_root);
        }
    private:
        node *_root=nullptr; 
        bool _check(node* root)
        {
            if (root == nullptr)
                return true;
            int bf = _high(root->_right) - _high(root->_left) ;
            if (bf != root->_bf)
            {
                cout << "bf:不一样" << endl;
                return false;
            }
            cout << "bf:" << bf <<" " << "root:" << (
                root->_val).first << endl;
            return _check(root->_left) && _check(root->_right);
        }
        int _high(node *root)
        {
            if (root == nullptr)
                return 0;
            int left = _high(root->_left);
            int right = _high(root->_right);
            if (left > right)
                return left + 1;
            else
                return right + 1;
        }   
    };
}
